#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class FindElements {
public:
    FindElements(TreeNode* root) {
        queue<TreeNode*> q;
        if (root) {
            root->val = 0;
            q.push(root);
        }
        while (!q.empty()) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left) {
                q.push(cur->left);
                cur->left->val = 2 * cur->val + 1;
            }
            if (cur->right) {
                q.push(cur->right);
                cur->right->val = 2 * cur->val + 2;
            }
        }
        theRoot = root;
    }
    
    bool find(int target) {
        if (target < 0)
            return false;
        
        TreeNode* curNode = theRoot;
        target++;
        // 获取二进制最左侧的1，右边补0，然后右移一位
        int bit = 1 << (31 - __builtin_clz(target)) >> 1;

        while (bit > 0 && curNode != NULL) {
            if ((target & bit) == 0)
                curNode = curNode->left;
            else
                curNode = curNode->right;
            bit >>= 1;
        }
        return curNode != NULL;
    }
private:
    TreeNode* theRoot;
};

/*
1. 可以使用set记录结果然后直接查找
2. 可以使用stl内置的binary_search()查找vector中的元素（前提将tree存于vector，自然升序存储）
3. 位运算查找：
从target二进制形式左边第一个1开始，将其与target后续的每一位进行&操作，结果 == 0说明该层对应二进制为0，进入左子树，== 1说明该层对应二进制为1，进入右子树

大致的想法是，首先将完全树中的值加1，得到的树就是下面这样的：
                1
            2       3
         4    5   6   7
       8  9 10 11 ...（放不下了就不写了，知道意思就好）

转换成二进制就是这样的
                1
        10              11
    100     101    110      111
1000  1001  ...

作者：cyanflxy
链接：https://leetcode-cn.com/problems/find-elements-in-a-contaminated-binary-tree/solution/bu-yong-setde-findfang-fa-by-cyanflxy/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */